package week3;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 *
 * 77. 组合
 * https://leetcode-cn.com/problems/combinations/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了99.99% 的用户
 * 内存消耗：39.9 MB, 在所有 Java 提交中击败了26.54% 的用户
 *
 */
public class Week3Combinations {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if(k <= 0 || n < k) {
            return list;
        }

        Deque<Integer> path = new ArrayDeque<Integer>();
        dfs(1, n, k, path, list);
        return list;
    }

    public void dfs(int begin, int n, int k, Deque<Integer> path, List<List<Integer>> list) {
        // 有效的答案
        if(k == 0) {
            list.add(new ArrayList<Integer>(path));
            return;
        }
        // 终止
        if(begin > n - k + 1) {
            return;
        }
        dfs(begin + 1, n, k, path, list);

        path.addLast(begin);
        dfs(begin + 1, n, k - 1, path, list);
        path.removeLast();
    }

}
